import java.util.Arrays;

/**
 * @author hewei
 * @version 1.0
 * @description: 740. 删除并获得点数
 * @date 2022/8/18 15:24
 */

public class DeleteAndEarn {

    public static void main(String[] args) {
        DeleteAndEarn deleteAndEarn = new DeleteAndEarn();
        int[] nums = {10, 8, 4, 2, 1, 3, 4, 8, 2, 9, 10, 4, 8, 5, 9, 1, 5, 1, 6, 8, 1, 1, 6, 7, 8, 9, 1, 7, 6, 8, 4, 5, 4, 1, 5, 9, 8, 6, 10, 6, 4, 3, 8, 4, 10, 8, 8, 10, 6, 4, 4, 4, 9, 6, 9, 10, 7, 1, 5, 3, 4, 4, 8, 1, 1, 2, 1, 4, 1, 1, 4, 9, 4, 7, 1, 5, 1, 10, 3, 5, 10, 3, 10, 2, 1, 10, 4, 1, 1, 4, 1, 2, 10, 9, 7, 10, 1, 2, 7, 5};
        System.out.println(deleteAndEarn.deleteAndEarn(nums));
    }

    public int deleteAndEarn1(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int no = 0;
        int yes = nums[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] == nums[i - 1]) {
                yes += nums[i];
            } else if (nums[i] == nums[i - 1] + 1) {
                int temp = yes;
                yes = no + nums[i];
                no = Math.max(temp, no);
            } else {
                int temp = Math.max(yes, no);
                yes = temp + nums[i];
                no = temp;
            }
        }
        return Math.max(no, yes);
    }

    public int deleteAndEarn(int[] nums) {
        int[] all = new int[10001];
        for (int num : nums) {
            all[num]++;
        }
        int l = all[1];
        int ll = 0;
        for (int i = 2; i < 10001; i++) {
            int temp = l;
            l = Math.max(l, ll + all[i] * i);
            ll = temp;
        }
        return Math.max(ll, l);
    }
}
